package leetcode.sort;

/**

 */
public class MergeSort {

    public static void main(String[] args) {
        int [] arr = new int[]{1,3,2,5,8,5,7,4,2,10,19,13,12};
        new MergeSort().mergetSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    private void mergetSort(int []nums){
        mergetSort(nums,0,nums.length-1);
    }
    private void mergetSort(int []nums,int l,int r){
        if(l>=r)
            return;

        int mid = l+(r-l)/2;
        mergetSort(nums,l,mid);
        mergetSort(nums,mid+1,r);
        merge(nums,l,mid,r);
    }

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private void merge(int [] arr,int l,int mid,int r){
        int []aux = new int[r-l+1];

        //先复制到辅助数组中
        for( int i = l ; i <= r; i ++ )
            aux[i-l] = arr[i]; //辅助空间和排序元素之间的偏移量

        int i =l,j = mid+1;
        for (int k = l; k <= r; k++) {
            if(i>mid){//[l...mid]已经搞定了，现在只考虑右边的部分
                arr[k] = aux[j-l];j++;
            }else if(j>r){//[mid...r]已经搞定了，现在只考虑左边的部分
                arr[k] = aux[i-l];i++;
            }else if(aux[i-l]>aux[j-l]){//左边的大于右边的
                arr[k] = aux[j-l];j++;
            }else {
                arr[k] = aux[i-l];i++;
            }
        }
    }

}